import operator

from polynomial.gcd import exgcd

__all__ = ["LiftingTree"]



class Node:

    __slots__ = ("inverse", "left", "poly", "right")

    def __init__(self):
        self.left = None
        self.right = None
        self.poly = None
        self.inverse = None


class LiftingTree:

    __slots__ = ("_list", "_poly", "_root")

    def __init__(self, poly, factor_list):
        self._list = factor_list
        self._root = self.create_tree(0, len(factor_list) - 1)
        self._poly = poly

    def create_tree(self, left, right):
        node = Node()
        if left == right:
            node.poly = self._list[left]
        else:
            mid = (left + right) >> 1
            node.left = self.create_tree(left, mid)
            node.right = self.create_tree(mid + 1, right)
            node.poly = node.left.poly * node.right.poly
            _g, node.left.inverse, node.right.inverse = exgcd(
                    node.left.poly, node.right.poly)
        return node

    def lift(self):
        type(self._root.poly).mod **= 2
        self._root.poly.init(self._poly.coeff)
        self._root.poly.to_monic()
        self.lift_node(self._root)

    def lift_node(self, node):
        if node.left is None:
            return
        F = node.poly
        PolyType = type(F)
        G, H = node.left.poly, node.right.poly
        g, h = node.left.inverse, node.right.inverse
        A = F - G * H
        q, r = divmod(g * A, H)
        deg = G.deg
        G += PolyType.trunc_mul(h, A, deg) + PolyType.trunc_mul(q, G, deg)
        H += r
        B = G * g + H * h
        B[0] -= 1
        q, r = divmod(g * B, H)
        g -= r
        h -= PolyType.trunc_mul(h, B, deg) + PolyType.trunc_mul(q, G, deg)
        self.lift_node(node.left)
        self.lift_node(node.right)

    @property
    def lift_result(self):
        stack = [self._root]
        while stack:
            node = stack.pop()
            if node.left is None:
                yield node.poly
            else:
                stack += node.right, node.left
